유용한 특징

예전에 적어두고 안쓰는 메모인데 어디 보관하기 애매해서 여기 블로그에다 적습니다. 내용이 맞는지 틀린지 몰루

단조성: Binary Search, 단조성이 보장되는 측도에서 최단거리문제는 dijkstra가능(단조증가측도의 최단경로, 단조감소측도의 최장경로)

볼록성: 볼록함수는 합, 합성곱, max?, 합성? 에 대해 닫혀있다.

주기성: 주기함수는 합에 대해 닫혀있다. 특히, a*cos(x+b)꼴의 합은 닫혀있다. 삼각함수 합차공식으로 풀어보면 바로 알 수 있다. sin(α±β)=sinαcosβ±cosαsinβ, cos(α±β)=cosαcosβ∓sinαsinβ

추이성(Transitive): 최단거리? 특히 플로이드? 같은거로 추이성 처리 용이하다. BOJ11097

격자에서 45도 기울어짐, 마름모꼴-> 반시계 45도 회전변환 = (x,y)=>1/sqrt(2)(x-y,x+y) 인데, 여기서 앞의 1/sqrt(2)를 제거하고 사용가능. 변환시 x에 음수좌표 생길 수 있고, y좌표는 최대값이 2배가 됨을 유의. 역변환시에는 (x+y)%2==0인 경우만 처리해야 함. 역변환: (x,y)=>((x+y)/2, (-x+y)/2), 관련문제: boj16436 boj17026(?) boj2983

맨해튼 거리 -> 45도 회전변환 -> 변환하면 거리가 |x0-x1|+|y0-y1| 에서 max(|x0-x1|,|y0-y1|) 이 된다.

구간합을 이산버전 적분구하는거로 보면 imos법(Range update point query) 보는 시야가 넓어짐.

Max in Minimums(or Min in Maximums): Binary Search

평균의 최대화, 가중평균의 최대화 문제는 선형이 아니라서 DP풀이가 안된다.(반례는 쉽게 찾을 수 있을 것이다) Parametric으로 접근해서, 어떤 집합 S에 대해 f: 식>x 꼴을 식2>0 꼴로 정리(우변을 0만 남기기)하면 O(N)정도에 판별가능한 선형식이 나오게 된다. 식정리의 중요성 및 익숙함에 속지 않는것의 중요성. 당연하게 식이 선형일것이라고 가정해버리는 실수 조심.

Online Persist 풀이: 대부분 Offline Query로 처리하면 Persistency 의존성 제거가능

모든 n^2쌍에 대해 n^2보다 빠른 계산: DnC or Stack등으로 묶어계산하여 합침

사전순: 그리디(그 순간 최적인걸 골라가면 전역최적임)

트리상의 쿼리 -> HLD, CD, LCA, 트리순회배열or오일러투어배열+세그(서브트리쿼리, 루트로부터의 경로쿼리), 자료구조 작은거 to 큰거 병합 기법(오프라인?)

Unrooted Tree O(n log n) 동형판별: Centroid(최대 2개)를 루트로 잡고 돌리면 됨

트리해싱: seq{자신 차수, set{자식들 해시값}}으로 진행하면 됨.

회전해서 같아지면 하나의 경우로 셈->번사이드 보조정리

x인것의 개수셀때 f(x)=x이상인것의 개수로 정의하는게 더 쉬울때가 종종 있다. 그럼 x인것 개수=f(x)-f(x-1)이 됨. MEX관련해서 그런 문제가 있었음 https://codeforces.com/contest/1527/problem/D